package com.LC._215;

import java.util.Random;

//class Solution{
//    public int findKthLargest(int[] nums, int k) {  // O(n)
//        shuffle(nums);  // shuffle the array
//        k = nums.length - k;
//        int lo = 0;
//        int hi = nums.length - 1;
//        while (lo < hi) {
//            final int j = partition(nums, lo, hi);  // partition the array
//            if(j < k) {
//                lo = j + 1;
//            } else if (j > k) {
//                hi = j - 1;
//            } else {
//                break;
//            }
//        }
//        return nums[k];
//    }
//    private int partition(int[] a, int lo, int hi) {    // O(n)
//        int i = lo;
//        int j = hi + 1;
//        while(true) {
//            while(i < hi &&// find item on left to swap
//                    less(a[++i], a[lo]));    // a[lo] acts as sentinel
//            while(j > lo && less(a[lo], a[--j]));
//            if(i >= j) {
//                break;
//            }
//            exch(a, i, j);
//        }
//        exch(a, lo, j); // swap with partitioning item
//        return j;
//    }
//
//    private void exch(int[] a, int i, int j) {
//        final int tmp = a[i];
//        a[i] = a[j];
//        a[j] = tmp;
//    }
//
//    private boolean less(int v, int w) {    // use to compare two elements
//        return v < w;
//    }
//    private void shuffle(int a[]) {
//        final Random random = new Random(); // use to shuffle the array
//        for(int ind = 1; ind < a.length; ind++) {
//            final int r = random.nextInt(ind + 1);  // [0, ind]
//            exch(a, ind, r);    // exchange a[ind] and a[r]
//        }
//    }
//
//    public static void main(String[] args) {
//        Solution sol = new Solution();
//        int[] nums = {3,2,1,5,6,4};
//        System.out.println(sol.findKthLargest(nums, 2));
//    }
//}
import java.util.Random;

 class Solution {

    private static Random random = new Random(System.currentTimeMillis());

    public int findKthLargest(int[] nums, int k) {
        int len = nums.length;
        int target = len - k;
        int left = 0;
        int right = len - 1;
        while (true) {
            int index = partition(nums, left, right);  //partition的返回值是标定点的位置
            if (index < target) {
                left = index + 1;
            } else if (index > target) {
                right = index - 1;
            } else {
                return nums[index];   // 找到第 k 大的元素
            }
        }
    }

    // 在区间 nums[left..right] 区间执行 partition 操作
    private int partition(int[] nums, int left, int right) {
        // 在区间随机选择一个元素作为标定点
        if (right > left) {
            int randomIndex = left + 1 + random.nextInt(right - left);  // [left, right]
            swap(nums, left, randomIndex); // 将标定点与第一个元素交换
        }

        int pivot = nums[left];// 将第一个元素作为标定点
        int j = left;
        for (int i = left + 1; i <= right; i++) {
            if (nums[i] < pivot) {  // 小于标定点的元素放在左边
                j++;
                swap(nums, j, i);// 将小于 pivot 的元素交换到左边
            }
        }
        swap(nums, left, j);    // 将标定点与左边的元素交换
        return j;
    }

    private void swap(int[] nums, int index1, int index2) {
        int temp = nums[index1];
        nums[index1] = nums[index2];
        nums[index2] = temp;
    }

     public static void main(String[] args) {
        Solution sol = new Solution();
        int[] nums = {3,2,1,5,6,4};
        System.out.println(sol.findKthLargest(nums, 2));
    }
}